package tree;

public class BinarySuccessor {

	 
	public static Node findRightSuccessor(Node root)
	{
	    while (root.left != null)
	        root=root.left;
	    return root;
	}
	 
	public static Node inorderSuccessor(Node root, int key, Node parent)
	{
	    if (root==null)
	        return null;
	    //get the node with the target value, now find the successor
	    if (root.value == key)
	    {
	        if (root.right != null)
	            return findRightSuccessor(root.right);
	        else
	            return parent;
	    }
	    
	    Node left=inorderSuccessor(root.left,key,root);
	    if (left != null)
	        return left;
	    return inorderSuccessor(root.right,key,parent);
	}
	 
	public static Node inorderSuccessor(Node root, int key)
	{
	    return inorderSuccessor(root,key,null);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(inorderSuccessor(Node.create1(), 7).value);
	}

}
